#pragma once
#include <iostream>
#include <set>
#include <map>
#include <assert.h>
using namespace std;
namespace cc
{
    enum colour
    {
        RED,
        BLACK
    };
    template<class K,class V>
    struct RBTnode
    {
        colour _col=RED;
        pair<K,V> _val;
        RBTnode<K,V>* _left=nullptr;
        RBTnode<K,V>* _right=nullptr;
        RBTnode<K,V>* _parent=nullptr;
        RBTnode(const pair<K,V>& x)
            :_val(x)
        {}
    };
    template<class K,class V>
    class RBT
    {
    public:
        typedef RBTnode<K,V> node;
        void reor(node* parent)
        {
            node* sub=parent->_left;
            node* subr=sub->_right;
            if(_root==parent)
            {
                _root=sub;
                sub->_parent=nullptr;
                sub->_right=parent;
                parent->_parent=sub;
                parent->_left=subr;
                if(subr)
                    subr->_parent=parent;
            }
            else
            {
                node* pparent=parent->_parent;
                if(pparent->_left==parent)
                    pparent->_left=sub;
                else
                    pparent->_right=sub;
                sub->_parent=pparent;
                sub->_right=parent;
                parent->_parent=sub;
                parent->_left=subr;
                if(subr)
                    subr->_parent=parent;
            }
        }
        void reol(node* parent)
        {
            node* sub=parent->_right;
            node* subl=sub->_left;
            if(_root==parent)
            {
                _root=sub;
                sub->_parent=nullptr;
                sub->_left=parent;
                parent->_right=subl;
                parent->_parent=sub;
                if(subl)
                    subl->_parent=parent;
            }
            else
            {
                node* pparent=parent->_parent;
                if(pparent->_left==parent)
                    pparent->_left=sub;
                else
                    pparent->_right=sub;
                sub->_parent=pparent;
                sub->_left=parent;
                parent->_right=subl;
                parent->_parent=sub;
                if(subl)
                    subl->_parent=parent;
            }
        }
        bool insert(const pair<K,V>& x)
        {
            if(_root==nullptr)
            {
                _root=new node(x);
                _root->_col=BLACK;
                return true;
            }
            node* parent=nullptr;
            node* cur=_root;
            while(cur)
            {
                if(x.first<cur->_val.first)
                {
                    parent=cur;
                    cur=cur->_left;
                }
                else if(x.first>cur->_val.first)
                {
                    parent=cur;
                    cur=cur->_right;
                }
                else 
                    return false;
            }           
            cur=new node(x);
            if(x.first<parent->_val.first)
                parent->_left=cur;
            else
                parent->_right=cur;
            cur->_parent=parent;
            //插入完成，准备旋转或是染色
            node* grandfather=parent->_parent;
            while(parent&&parent->_col==RED)
            {
                if(grandfather->_left==parent)
                {
                    node* uncle=grandfather->_right;
                    if(uncle&&uncle->_col==RED)
                    {
                        uncle->_col=parent->_col=BLACK;
                        if(_root!=grandfather)
                            grandfather->_col=RED;
                    }
                    if(parent->_left==cur)
                    {
                        if(uncle&&uncle->_col==BLACK)
                        {
                            //染色加单旋
                            reor(grandfather);
                            parent->_col=BLACK;
                            grandfather->_col=RED;
                             break;
                        }
                        else
                        {
                            reor(grandfather);
                            parent->_col=BLACK;
                            grandfather->_col=RED;
                             break;
                        }
                    }
                    else
                    {
                        if(uncle&&uncle->_col==BLACK)
                        {
                            reol(parent);
                            reor(grandfather);
                            grandfather->_col=RED;
                            cur->_col=BLACK;
                             break;
                        }
                        else
                        {
                            reol(parent);
                            reor(grandfather);
                            grandfather->_col=RED;
                            cur->_col=BLACK;
                             break;
                        }
                    }
                }
                else
                {
                    node* uncle=grandfather->_left;
                    if(uncle&&uncle->_col==RED)
                    {
                        uncle->_col=parent->_col=BLACK;
                        if(_root!=grandfather)
                            grandfather->_col=BLACK;
                    }
                    if(parent->_left==cur)
                    {
                        if(uncle&&uncle->_col==BLACK)
                        {
                            reor(parent);
                            reol(grandfather);
                            cur->_col=BLACK;
                            grandfather->_col=RED;
                             break;
                        }
                        else
                        {
                            reor(parent);
                            reol(grandfather);
                            cur->_col=BLACK;
                            grandfather->_col=RED;
                             break;
                        }
                    }
                    else
                    {
                        if(uncle&&uncle->_col==BLACK)
                        {
                            reol(grandfather);
                            parent->_col=BLACK;
                            grandfather->_col=RED;
                             break;
                        }
                        else
                        {
                            reol(grandfather);
                            parent->_col=BLACK;
                            grandfather->_col=RED;
                             break;
                        }
                    }
                }
                cur=grandfather;
                parent=cur->_parent;
                grandfather=parent->_parent;
            }
            return true;
        }
        void check()
        {
            int x=0;
            _check(_root,x);
        }
    private:
        node* _root=nullptr;
        void _check(node *root,int x)
        {
            if(root==nullptr)
            {
                cout<<x<<endl;
                return;
            }
            if(root->_col==RED&&(root->_parent&&root->_parent->_col==RED))
            {
                cout<<"有相同的红色节点出现"<<endl;
                assert(false);
            }
            if(root->_col==BLACK)
                x++;
            _check(root->_left,x);
            _check(root->_right,x);
        }
    };
}